Recently, wireless (cellular, 802.11 wireless LANs, etc) networks have gained significant interest due to potential high data rate connectivity, very low deployment cost, and free or low-cost network access to users. Several enterprises and universities have deployed large scale wireless networks to service a number of users.
Numerous urban areas are already covered with dense deployments of wireless networks and efforts to form community mesh networks using them are under way (FON WiFi Community. http://www.fon.com/en/.).
Wireless networks and in particular IEEE 802.11 networks, however, suffer from serious interference problems limiting their capacity due to the broadcast nature of the wireless medium and their use of the unlicensed spectrum band. Sectorized antennas are attractive solutions to reduce wireless interference through higher spatial reuse. They can concentrate radio signal energy in a particular direction, instead of radiating it in all directions like their omni-directional counterpart. There exist primarily two approaches to exploit directional communication in wireless networks: directional MAC protocols and topology control protocols. Directional MAC protocols (R. Choudhury and N. H. Vaidya. “Deafness: A Mac Problem in Ad Hoc Networks when using Directional Antennas.” In Proc. IEEE ICNP, October 2004—and Y. Ko, V. Shankarkumar, and N. H. Vaidya. “Medium Access Control Protocols Using Directional Antennas in Ad Hoc Networks”. In Proc. IEEE INFOCOM, March 2000) aim to achieve higher spatial reuse by switching between different sectors to communicate to different neighbors at a very fast (per-packet) time scale. They also require modifications to the IEEE 802.11 MAC protocol to combat deafness and directional hidden terminal problem (R. Choudhury, X. Yang, R. Ramanathan, and N. H Vaidya. “Using Directional Antennas for Medium Access Control in Ad Hoc Networks” In Proc. ACM MobiCom, September 2002). On the other hand, topology control protocols (Z. Huang, C. Shen, C. Srisathapornphat, and C. Jaikaeo. “Topology Control for Ad hoc Networks with Directional Antennas” In IEEE Int. Conference on Computer Communications and Networks, 2002.—Zhuochuan Huang and Chien-Chung Shen. “Multibeam Antenna-based Topology Control with Directional Power Intensity for Ad Hoc Networks” 5(5), 2006—U. Kumar, H. Gupta, and S. R. Das. “A Topology Control Approach to using Directional Antennas in Wireless Mesh Networks” In Proc. ICC, 2006—K. Sundaresan, W. Wang, and S. Eidenbenz. “Algorithmic Aspects of Communication in Ad-hoc Networks with Smart Antennas” In Proc. ACM MobiHoc, 2006) activate multiple sectors simultaneously at slower time scales (on the order of minutes or more) at the potential expense of performance without requiring complex modifications to the standard IEEE 802.11 MAC protocol.
All these proposed topology control solutions use simplistic interference model assumptions (such as pairwise interference) and use adaptations of graph theoretic algorithms. They ignore several practical considerations and are evaluated only through simulation studies. On the other hand, recent measurement studies on densely deployed IEEE 802.11 networks (M. Blanco, R. Kokku, K. Ramachandran, S. Rangarajan, and K. Sundaresan. On the Effectiveness of Switched Beam Antennas in Indoor Environments. In In Proc. Passive and Active Measurements Conference (PAM), 2008—A. P. Subramanian, H. Lundgren, and T. Salonidis. “Experimental Characterization of Sectorized Antennas in Dense 802.11 Wireless Mesh Networks.” In Proc. ACM MobiHoc, 2009.) have shown that common design assumptions such as usage of geographically pointing sectors and sector independence on multi-sector activation are sub-optimal in reflection-rich dense deployments. These studies have also investigated the effect of physical layer capture on reducing directional hidden terminal problem and have shown that sectorized antennas can provide higher spatial reuse opportunities. However, these observations have not been translated to practical protocols that can extract the capacity gains of antenna sectorization in real-world dense IEEE 802.11 wireless environments.
A majority of past work on the use of sectorized antennas and topology control in IEEE 802.11 based wireless networks has focused on analytical studies, and protocol design and evaluation through simulations. Kumar et al. (U. Kumar, H. Gupta, and S. R. Das. “A Topology Control Approach to using Directional Antennas in Wireless Mesh Networks” In Proc. ICC, 2006) uses an antenna model consisting of multiple single-sector antennas and propose a centralized algorithm to construct a minimum degree spanning tree in a mesh network. Huang et al. (Z. Huang, C. Shen, C. Srisathapornphat, and C. Jaikaeo. “Topology Control for Ad hoc Networks with Directional Antennas” In IEEE Int. Conference on Computer Communications and Networks, 2002.—Zhuochuan Huang and Chien-Chung Shen. “Multibeam Antenna-based Topology Control with Directional Power Intensity for Ad Hoc Networks” 5(5), 2006) propose two different topology control approaches which use transmission power adjustments and multi-sector antennas. They assume simplified antenna and network interference models, and propose a graph coloring based approach. Finally, Sundaresan et al. (K. Sundaresan, W. Wang, and S. Eidenbenz. “Algorithmic Aspects of Communication in Ad-hoc Networks with Smart Antennas” In Proc. ACM MobiHoc, 2006.) consider the problem of determining the (antenna) communication pattern to be used by nodes in a mesh network and formulate it as interference minimization when using “smart antennas” (digital adaptive arrays). All the current approaches for topology control uses idealized antenna models, assume pair-wise interference model, propose solutions based on graph theoretic algorithms, and have only been evaluated through simulations.